package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.net.URL;
import java.net.URLDecoder;

/**
 * 分析：
 * 
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1845 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1845.class.getResource("P1845.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		int[] ps = primes((int)Math.sqrt(50000000)+1);
		String line = stdin.readLine();
		String[] tmp = line.trim().split("\\s+");
		int A = Integer.valueOf(tmp[0]);
		int B = Integer.valueOf(tmp[1]);
		System.out.println(modulo(A, B, ps));
	}

	private static int modulo(long A, long B, int[] ps) {

		int[] v = getV();
		int q = 9901;
		BigInteger n9901 = BigInteger.valueOf(q);
		
		while (A%q == 0) A /= q;	//do not care prime factor: 9901
		
		int[][] fs = factors(A, ps);
		int m = 1;
		for (int i = 0; i < fs.length; i ++) {
			int p = fs[i][0];
			int a = fs[i][1];
			if ((p-1)%q == 0) {
				m *= ((long)a*(long)B+1)%q;
			} else {
				BigInteger exp = BigInteger.valueOf(((long)a*(long)B+1)%(q-1));
				long r = BigInteger.valueOf(p).modPow(exp, n9901).longValue()-1;
				m *= (r*(long)v[(p-1)%q])%q;
				m %= q;	//漏了这一步很容易就会出现溢出
			}
		}
		int n = m%9901;
		return (n < 0)?(n+9901):n;
	}
	
	/**
	 * v[i]*i = 1 (mod 9901)
	 * @return
	 */
	private static int[] getV() {
		
		//利用9901的原根2加速计算v
		int[] tmp = new int[9901];
		tmp[0] = 1;
		for (int i = 1; i < 9901; i ++) {
			tmp[i] = (tmp[i-1]*2)%9901;
		}
		
		int[] v = new int[9901];
		v[0] = -1;
		for (int i = 0; i < 9901; i ++) {
			v[tmp[i]] = tmp[9900-i];
		}
		return v;
	}
	
	/**
	 * ps is all primes number less than sqrt(n)
	 * @param n
	 * @param ps
	 * @return
	 */
	private static int[][] factors(long n, int[] ps) {

		int[] as = new int[ps.length];
		for (int i = 0; i < as.length; i ++) {
			if (n >= ps[i]) {
				while (n%ps[i] == 0) {
					n /= ps[i];
					as[i] ++;
				}
			}
		}
		
		int count = 0;
		for (int i = 0; i < as.length; i ++) {
			if (as[i] > 0) {
				count ++;
			}
		}
		if (n > 1) count ++;
		
		int[][] fs = new int[count][];
		int index = 0;
		for (int i = 0; i < as.length; i ++) {
			if (as[i] > 0) {
				fs[index] = new int[2];
				fs[index][0] = ps[i];
				fs[index][1] = as[i];
				index ++;
			}
		}
		if (n > 1) {
			fs[count-1] = new int[2];
			fs[count-1][0] = (int)n;
			fs[count-1][1] = 1;
		}
		return fs;
	}
	
	private static int[] primes(int m) {
		
		if (m <= 1) {
			return new int[0];
		} else if (m == 2) {
			return new int[] {2};
		} else {
			int count = 0;
			int[] ns = new int[m];
			for (int i = 0; i < m; i ++) ns[i] = i;
			ns[0] = ns[1] = 0;
			
			int index = 2;
			int p = 0;
			while (index < m) {
				if (ns[index] != 0) {
					count ++;
					p = index;
					for (int j = (p<<1); j < m; j += p) {
						ns[j] = 0;
					}
				}
				index ++;
			}
			
			index = 0;
			int[] ps = new int[count];
			for (int i = 0; i < m; i ++) {
				if (ns[i] != 0) {
					ps[index ++] = i;
				}
			}

			return ps;
		}
	}
}